package com.example.demo;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author sunny
 */
public class TreeNodeTest {

    static class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value, TreeNode left, TreeNode right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int value) {
            this.value = value;
        }
    }


    public static TreeNode build(){




        TreeNode root8 = new TreeNode(8);
        TreeNode root7 = new TreeNode(7);
        TreeNode root6 = new TreeNode(6);
        TreeNode root5 = new TreeNode(5);
        TreeNode root4 = new TreeNode(4,root7,root8);
        TreeNode root3 = new TreeNode(3,null,root6);
        TreeNode root2 = new TreeNode(2,root4,root5);
        TreeNode root = new TreeNode(1,root2,root3);
        return root;
    }

    /**
     * 前序遍历 中序遍历 后序遍历
     *  根左右   左根右  左右根
     */
    /**
     *      1
     *    2    3
     *   4 5    6
     *  7  8
     *
     *  print 1 sout1 print 2 sout2  print 4 sout 4 print 7 sout 7
     */
    public static void print (TreeNode root){
        if(root==null){
            return;
        }
        if(root!=null){

            print(root.left);
            System.out.println(root.value);
            print(root.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root = build();
        printFinish(root);
    }

    /**
     * 前序遍历 中序遍历 后序遍历
     *  根左右   左根右  左右根
     */
    /**
     *      1
     *    2    3
     *   4 5    6
     *  7  8
     *
     *  print 1 sout1 print 2 sout2  print 4 sout 4 print 7 sout 7
     */
    public static void printFinish(TreeNode root){
        if(root==null){
            return;
        }
        List<TreeNode> list = new ArrayList<>();
//        list.add(root);
//        list.add(root.left);
//        list.add(root.right);
//        list.add(root.left.left);
//        list.add(root.left.right);
        list.add(root);
        boolean flag = true;
        while(root!=null){

            if(root.left!=null){
                list.add(root.left);
            }
            if(root.right!=null){
                list.add(root.right);
            }
            if(flag){
                root = root.left;
                flag = false;
            }else {
                root = root.right;
            }

        }
        for (TreeNode ndoe :
               list ) {
            System.out.println(ndoe.value);
        }
    }
    public static void frontPrint(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null && (!stack.isEmpty())){
            if(root!=null){
                System.out.println(root.value);
                stack.push(root);
                root = root.left;
            }else {
                TreeNode pop = stack.pop();
                root = pop.right;
            }
        }

    }

    /**
     * 前序遍历 中序遍历 后序遍历
     *  根左右   左根右  左右根
     */
    /**
     *      1
     *    2    3
     *   4 5    6
     *  7  8
     *
     *  print 1 sout1 print 2 sout2  print 4 sout 4 print 7 sout 7
     */
    public static void middlePrint(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null && (!stack.isEmpty())){
            if(root!=null){
                stack.push(root);
                root = root.left;
            }else {
                TreeNode pop = stack.pop();
                System.out.println(pop.value);
                root = pop.right;
            }
        }

    }

    public static void houPrint(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        List<TreeNode> list = new ArrayList<>();
        while(root!=null && (!stack.isEmpty())){
            if(root!=null){
                list.add(root);
                stack.push(root);
                root = root.right;
            }else {
                TreeNode pop = stack.pop();

                root = pop.left;
            }
        }
        for(int i = list.size()-1;i>=0;i--){
            System.out.println(list.get(i));
        }

    }
}
